package com.alex.statistics.method.explorationAnalysis;

import java.util.List;
import java.util.*;

/**
 * DBSCAN聚类核心算法
 */
public class DBSCANClusterer {
    private final double eps;
    private final int minPts;
    private final List<DBSCANDataPoint> noisePoints = new ArrayList<>();

    public DBSCANClusterer(double eps, int minPts) {
        this.eps = eps;
        this.minPts = minPts;
    }

    public List<List<DBSCANDataPoint>> cluster(List<DBSCANDataPoint> points) {
        List<List<DBSCANDataPoint>> clusters = new ArrayList<>();
        Set<DBSCANDataPoint> visited = new HashSet<>();

        for (DBSCANDataPoint point : points) {
            if (!visited.contains(point)) {
                visited.add(point);
                List<DBSCANDataPoint> neighbors = findNeighbors(point, points);

                if (neighbors.size() < minPts) {
                    point.setNoise(true);
                    noisePoints.add(point);
                } else {
                    List<DBSCANDataPoint> cluster = new ArrayList<>();
                    expandCluster(points, point, neighbors, cluster, visited);
                    clusters.add(cluster);
                }
            }
        }
        return clusters;
    }

    private void expandCluster(List<DBSCANDataPoint> points, DBSCANDataPoint point,
                               List<DBSCANDataPoint> neighbors, List<DBSCANDataPoint> cluster,
                               Set<DBSCANDataPoint> visited) {
        cluster.add(point);
        Queue<DBSCANDataPoint> queue = new LinkedList<>(neighbors);

        while (!queue.isEmpty()) {
            DBSCANDataPoint current = queue.poll();
            if (!visited.contains(current)) {
                visited.add(current);
                List<DBSCANDataPoint> currentNeighbors = findNeighbors(current, points);
                if (currentNeighbors.size() >= minPts) {
                    queue.addAll(currentNeighbors);
                }
            }
            if (current.getClusterId() == -1) {
                cluster.add(current);
            }
        }
    }

    private List<DBSCANDataPoint> findNeighbors(DBSCANDataPoint point, List<DBSCANDataPoint> points) {
        List<DBSCANDataPoint> neighbors = new ArrayList<>();
        for (DBSCANDataPoint p : points) {
            if (point.distanceTo(p) <= eps) {
                neighbors.add(p);
            }
        }
        return neighbors;
    }

    public List<DBSCANDataPoint> getNoisePoints() {
        return noisePoints;
    }
}